﻿#include<stdio.h>
#include<stdlib.h>
typedef int* LIST;
void Print(int n, int* A);
void merge(int s, int m, int t, LIST A, LIST B);
void mergepass(int n, int h, LIST A, LIST B);
void mergesort(int n, LIST A);
void quicksort(LIST A, int left, int right);
void selectsort(LIST A, int n);
void swap(int* ad_i, int* ad_j);

int main()
{
	int n;
	int* array,*array_1,*array_2,*array_3;
	FILE* fp;
	if (fopen_s(&fp, "input.txt", "r") != 0) {
		printf("打开失败\n");
		return 1;
	}
	fscanf_s(fp, "%d", &n,1);
	array = (int*)malloc(n * sizeof(int));
	for (int i = 0; i < n; i++)
	{
		fscanf_s(fp, "%d", array+i, 1);
	}
	fclose(fp);

	printf("未排序时：\n");
	Print(n,array);

	array_1 = (int*)malloc(n * sizeof(int));
	for (int i = 0; i < n; i++)
		array_1[i] = array[i];
	printf("归并排序后：\n");
	mergesort(n, array_1);
	Print(n, array_1);

	array_2 = (int*)malloc(n * sizeof(int));
	for (int i = 0; i < n; i++)
		array_2[i] = array[i];
	printf("快速排序后：\n");
	quicksort(array_2,0,n-1);
	Print(n, array_2);

	array_3 = (int*)malloc(n * sizeof(int));
	for (int i = 0; i < n; i++)
		array_3[i] = array[i];
	printf("选择排序后：\n");
	selectsort(array_3,n);
	Print(n, array_3);
}

void Print(int n, int* A)
{
	for (int i = 0; i < n; i++)
		printf("%d,", A[i]);
	printf("\n");
}

//两有序序列合并
void merge(int s, int m, int t, LIST A, LIST B)
{
	int i=s, j=m+1, k=s;
	while (i <= m && j <= t)
		B[k++] = (A[i] <= A[j]) ? A[i++] : A[j++];
	while (i <= m)
		B[k++] = A[i++];
	while (j <= t)
		B[k++] = A[j++];
}

//全部按h个数划分并两两合并
void mergepass(int n, int h, LIST A, LIST B)
{
	int i, t;
	for (i = 0; i + 2 * h - 1 < n; i += 2 * h)
		merge(i, i + h - 1, i + 2 * h - 1, A, B);
	if (i + h - 1 < n)
		merge(i, i + h - 1, n-1, A, B);
	else//包括i<=n且i+h-1>=n的情况，也处理了mergesort中第二轮复制超了
		for (t = i; t < n; t++)
			B[t] = A[t];
}

//遍历h合并
void mergesort(int n, LIST A)
{
	int h = 1;
	LIST B;
	B = (int*)malloc(n * sizeof(int));
	while (h < n) {
		mergepass(n, h, A, B);
		h = 2 * h;
		mergepass(n, h, B, A);
		h = 2 * h;
	}
}

//快速排序
void quicksort(LIST A, int left, int right)
{
	int i=left, j=right;
	int x = A[(left + right) / 2];
	//i,j左右逼近，确定x左右分区
	do {
		while (i < right && A[i] < x)	i++;
		while (left < j && A[j]>x)	j--;
		if (i <= j) {
			swap(A + i, A + j);
			i++;
			j--;
		}
	} while (i <= j);
	//当i,j相遇，已完成左右分区
	if (left < j)
		quicksort(A, left, j);
	if (right > i)
		quicksort(A, i, right);
}

//选择排序
void selectsort(LIST A, int n)
{
	int low, lowindex;
	for (int i = 0; i < n - 1; i++)
	{
		low = A[i];
		lowindex = i;
		for (int j = i + 1; j < n; j++)
		{
			if (A[j] < low) {
				low = A[j];
				lowindex = j;
			}
		}
		if (i!=lowindex) {
			swap(A + lowindex, A + i);
		}
	}
}

void swap(int* ad_i, int* ad_j)
{
	int temp = *ad_i;
	*ad_i = *ad_j;
	*ad_j = temp;
}